package class17;

import java.util.*;

/**
 * @author YZY
 * @since 2022/8/17 11:10
 * 打印一个字符串的全部子序列
 */
public class Code03_PrintAllSubsequences {

    // 包含重复的子序列
    public static List<String> allSubsequences1(String str) {
        char[] arr = str.toCharArray();
        String s = "";
        List<String> result = new ArrayList<>();
        process1(arr, result, s, 0);
        return result;
    }

    public static void process1(char[] arr, List<String> result, String s, int index) {
        if (index == arr.length) {
            result.add(s);
            return;
        }
        process1(arr, result, s, index + 1);
        process1(arr, result, s + arr[index], index + 1);
    }

    // 不包含重复的子序列
    public static List<String> allSubsequences2(String str) {
        char[] arr = str.toCharArray();
        String s = "";
        Set<String> set = new HashSet<>();
        process2(arr, set, s, 0);
        return new ArrayList<>(set);
    }

    private static void process2(char[] arr, Set<String> set, String s, int index) {
        if (index == arr.length) {
            set.add(s);
            return;
        }
        process2(arr, set, s, index + 1);
        process2(arr, set, s + arr[index], index + 1);
    }

    public static void main(String[] args) {
        System.out.println(allSubsequences1("accc"));
        System.out.println(allSubsequences2("accc"));
    }

}
